package com.qf.pojo.day01;

import java.util.HashSet;
import java.util.Set;

/**
 * 18. 如何判断链表是否有环？
 *
 * @author lixu
 */
public class isCycleDemo {

    private static class Node<T> {
        T value;
        Node<T> next;

        public Node(T value) {
            this.value = value;
        }
    }
    //Ctrl + F  Ctrl +R  

    public static void main(String[] args) {

        Node node1 = new Node(5);
        Node node2 = new Node(8);
        Node node3 = new Node(2);
        Node node4 = new Node(1);
        Node node5 = new Node(9);
        Node node6 = new Node(7);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        //有环
        node6.next=node3;

        System.out.println("是否有环:" + isCycle2(node1));


    }

    /**
     *      * 时间复杂度：  O（n)
     *      * 空间复杂度:  ：O(1)
     *
     *
     *      使用追赶的方法，设定两个指针slow、fast
     *       从头指针开始，每次fast指针前进2步, slow指针前进1步。
     *       如存在环，则两者相遇；如不存在环，fast遇到NULL退出
     * @param node1
     * @return
     */
    private static boolean isCycle2(Node node1) {
        Node fastNode = node1;//1
        Node slowNode = node1;//1
        //慢 前进1个
        //fastNode!= null 节点为偶数时
        //fastNode.next!=null 节点为奇数时

        while (fastNode!=null && fastNode.next!=null){
            fastNode = fastNode.next.next;
            slowNode = slowNode.next;
            if(fastNode==slowNode){
                return true;
            }
        }
        return false;

    }


    /**
     * 时间复杂度为 O(n^2)
     * 空间复杂度为 O（1）
     * @param node1
     * @return
     */
    private static boolean isCycle1(Node node1) {
        Node B = node1.next;
        Node A = null;
        int i = 1;//B的角标
        while (B!=null){
            //A的角标
            int j = 0;
            A = node1;
            while (j < i){
                if(A==B){
                    return true;//有环
                }
                j++;
                A=A.next;
            }
            B=B.next;//B往下走了
            i++;
        }
        return false;//无环

    }

    //容器
    private static Set<Node> nodeSet = new HashSet<Node>();// 空间复杂度O(n)

    /**
     * 算法：
     * 是否有环
     * true: 有环
     * false:没环
     *
     * 时间复杂度： 最好：O(1)  最坏 : O（n)
     * 空间复杂度:  最好：O(1)  最坏 : O(n+1)  平均：  (n+2)/2= n/2+1 ~n
     *
     * @param node1
     * @return
     */
    private static boolean isCycle(Node node1) {//Node node1 : 链表 规模  不算

        //p : 临时节点
        Node p = node1;//赋值链表的头节点  //1

        while (p != null) {//  n行
            //System.out.print(p.value + " ");
            //当前p是头节点
            if (nodeSet.contains(p)) { //1
                //有环
                return true;
            }
            nodeSet.add(p);//1
            p = p.next;//1
        }
        //无环
        return false;//1

    }


}
